# 归并排序
def merge(list1, list2):
    listall = []
    while len(list1) > 0 and len(list2) > 0:
        if list1[0] < list2[0]:
            listall.append(list1[0])
            del list1[0]
        else:
            listall.append(list2[0])
            del list2[0]
    listall.extend(list1)
    listall.extend(list2)

    return listall


list1 = [11, 3, 5, 7, 9]
list2 = [8, 4, 2, 6]
list1.sort()  # 排序
list2.sort()
print(merge(list1, list2))


#归并排序下标版
'''
def   merge(mylist1,mylist2):
    mylistall=[]
    i1=0
    i2=0
    while  i1< len(mylist1) and  i2 <len(mylist2)>0:  #有一个结束，没有必须要对比
        if  mylist1[i1] <mylist2[i2]: #谁大选谁
            mylistall.append(mylist1[i1])
            i1+=1  #下标移动
        elif mylist1[i1] >mylist2[i2]:
            mylistall.append(mylist2[i2])
            i2+=1  #下标移动
        else:
            mylistall.append(mylist2[i2])
            i1+=1
            i2+=1

    while  i1<len(mylist1):  #粘贴尾部
        mylistall.append(mylist1[i1])
        i1+=1
    while i2 < len(mylist2):
        mylistall.append(mylist2[i2])
        i2 += 1
    #mylistall.extend(mylist1)
    #mylistall.extend(mylist2)

    return  mylistall
'''